package lc;
import java.util.*;
import java.util.stream.Collectors;

import org.junit.*;
public class Ex138 {
    class Solution {
        public int longestConsecutive(int[] nums) {
            if (nums.length == 0) return 0;
            Set<Integer> set = Arrays.stream(nums).boxed().collect(Collectors.toSet());
            int res = 1;
            UnionFindSet ufs = new UnionFindSet(nums);
            for (int i = 0; i < nums.length; i++) {
                if (set.contains(nums[i] + 1)) {
                    int t = ufs.union(nums[i], nums[i] + 1);
                    res = Math.max(t, res);
                }
            }
            return res;
        }
    
        class UnionFindSet {
            Map<Integer, Integer> parent;
            Map<Integer, Integer> weight;
    
            public UnionFindSet(int[] nums) {
                int len = nums.length;
                parent = new HashMap<>();
                weight = new HashMap<>();
                for (int i = 0; i < len; i++) {
                    parent.put(nums[i], nums[i]);  
                    weight.put(nums[i], 1);
                }
            }
    
            public int find(int cur) {
                int p;
                if ((p = parent.get(cur)) == cur) {
                    return cur;
                }
                int r = find(p);
                parent.put(cur, r);
                return r;
            }
    
            public boolean isConnnect(int n1, int n2) {
                return parent.get(n1) == parent.get(n2);
            }
    
            public int union(int n1, int n2) {
                int r1 = find(n1), r2 = find(n2);
                if (r1 == r2) return weight.get(r1);
                else {
                    int t = weight.get(r1) + weight.get(r2);
                    weight.put(r1, t);
                    parent.put(r2, r1);
                    return t;
                }
            }
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{100,4,200,1,3,2};
        System.out.println(s.longestConsecutive(nums));
    }
}
